package com.sicheng.algorithm.string;

import java.util.LinkedHashMap;
import java.util.Map;

public class FirstNotRepeatingChar {

    /**
     * 题目描述
     * 在一个字符串中找到第一个只出现一次的字符，并返回它的位置。字符串只包含 ASCII 码字符。
     * <p>
     * Input: abacc
     * Output: b
     */
    public static void main(String[] args) {

        String str = "baccdi";
        int firstNotRepeatingChar = firstNotRepeatingChar(str);

        if (firstNotRepeatingChar != -1)
            System.out.println(str.charAt(firstNotRepeatingChar));

    }


    /**
     * 最直观的解法是使用 HashMap 对出现次数进行统计：
     * 字符做为 key，出现次数作为 value，遍历字符串每次都将 key 对应的 value 加 1。
     * <p>
     * 最后再遍历这个 HashMap 就可以找出出现次数为 1 的字符。
     */
    public static int firstNotRepeatingChar(String str) {
        Map<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < str.length(); i++) {
            char current = str.charAt(i);
            if (map.containsKey(current)) {
                Integer value = map.get(current) + 1;
                map.put(current, value);
            } else
                map.put(current, 1);
        }

        int result = -1;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                result = entry.getKey();
                break;
            }
        }
        // 没有不重复的值
        if (result == -1)
            return -1;

        return str.indexOf(result);
    }
}
